package com.duoduo.深度广度优先;

import com.duoduo.TreeNode;

/**
 * @program: algorithm
 * @description: 二叉搜索树的第k大节点 54
 * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: root = [3,1,4,null,2], k = 1
 *    3
 *   / \
 *  1   4
 *   \
 *    2
 * 输出: 4
 * @author: chaidl  ！
 * @create: 2022-03-03 15:06
 */
public class 二叉搜索树的第k大节点 {
    int res,k;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        dfs(root);
        return res;
    }

    /**
     * 采用广度优先的中序遍历倒序
     * @param root
     */
    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        //先从左右边的叶子结点遍历
        dfs(root.right);
        //如果k为0，表示已经找到了后续的遍历已变得毫无意义
        if (k==0){
            return;
        }
        // 当k=0的时候,将此时root节点的值返回
        if (--k==0){
            res = root.val;
        }
        dfs(root.left);
    }
}
